package class21;

import java.util.HashMap;
import java.util.Map;

/**
 * @author YZY
 * @since 2022/8/22 16:16
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 认为值相同的货币没有任何不同，
 * 返回组成aim的方法数
 * 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * 方法：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 */
public class Code04_CoinsWaySameValueSamePaper {

    // 记录信息
    public static class Info {
        public int[] coins;
        public int[] coinsCount;

        public Info(int[] coins, int[] coinsCount) {
            this.coins = coins;
            this.coinsCount = coinsCount;
        }
    }

    // 转换数据
    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int n = map.size();
        int[] coins = new int[n];
        int[] coinsCount = new int[n];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            coins[index] = entry.getKey();
            coinsCount[index++] = entry.getValue();
        }
        return new Info(coins, coinsCount);
    }

    /**
     * 暴力尝试
     */
    public static int coinsWay1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process1(info.coins, info.coinsCount, 0, aim);
    }

    private static int process1(int[] coins, int[] coinsCount, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int sheet = 0; rest >= sheet * coins[index] && sheet <= coinsCount[index]; ++sheet) {
            ways += process1(coins, coinsCount, index + 1, rest - sheet * coins[index]);
        }
        return ways;
    }

    /**
     * 记忆化搜索
     */
    public static int coinsWay2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[][] dp = new int[info.coins.length + 1][aim + 1];
        return process2(info.coins, info.coinsCount, 0, aim, dp);
    }

    private static int process2(int[] coins, int[] coinsCount, int index, int rest, int[][] dp) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        if (dp[index][rest] != 0) {
            return dp[index][rest];
        }
        int ways = 0;
        for (int sheet = 0; sheet <= coinsCount[index] && rest >= sheet * coins[index]; ++sheet) {
            ways += process2(coins, coinsCount, index + 1, rest - sheet * coins[index], dp);
        }
        return dp[index][rest] = ways;
    }

    /**
     * 动态规划
     */
    public static int coinsWay3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] coinsCount = info.coinsCount;
        int n = coins.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; --index) {
            for (int rest = 0; rest <= aim; ++rest) {
                int ways = 0;
                for (int sheet = 0; sheet <= coinsCount[index] && rest >= sheet * coins[index]; ++sheet) {
                    ways += dp[index + 1][rest - sheet * coins[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    /**
     * 动态规划 - 优化
     */
    public static int coinsWay4(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] coinsCount = info.coinsCount;
        int n = coins.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; --index) {
            for (int rest = 0; rest <= aim; ++rest) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest >= coins[index]) {
                    dp[index][rest] += dp[index][rest - coins[index]];
                }
                if (rest >= coins[index] * (coinsCount[index] + 1)) {
                    dp[index][rest] -= dp[index + 1][rest - coins[index] * (coinsCount[index] + 1)];
                }
            }
        }
        return dp[0][aim];
    }

    // 为了测试
    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 为了测试
    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 20;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = coinsWay2(arr, aim);
            int ans2 = coinsWay3(arr, aim);
            int ans3 = coinsWay4(arr, aim);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
                break;
            }
        }
        System.out.println("测试结束");
    }

}
